TSP 외판원 순회 문제

비용이 최소가 되는 해밀턴 사이클을 찾는 문제이다.

N <= 11 일 때 O(N!) 의 브루트포스 풀이가 가능하다. N <= 12 일 때 백트래킹 풀이가 가능하다. N <= 16 일 때 DP 와 BitMasking 을 사용하여 O(N^2 * 2^n) 풀이가 가능하다.

1, 2, 3, 4, 5 어느 정점에서 출발하든 최적의 순회 경로는 동일하므로, 한 정점에서 시작하는 것만 고려해도 된다.

Brute-Force 풀이

모든 가능한 경로의 조합을 구하고, 그 중에서 최단 경로를 찾는다.
가능한 경로의 조합은 N! 이므로, 시간 복잡도는 O(N!) 이다.

DP + Bitmasking

Held-Karp 알고리즘에 기반한 풀이라고 한다.
bit-masking

아이디어

1. 각 도시의 부분 집합에 대한 최적의 경로를 계산하고 저장하기 위해 2차원 DP 테이블을 사용한다.
2. 비트마스킹을 사용해서 각 도시의 부분 집합을 표현하고, 이를 DP 테이블의 인덱스로 사용한다.

구현하기

1. DP 테이블은 [n][2^n] 이다. (n 은 도시의 수)
2. dp[i][j] 는 도시 i 를 마지막으로 방문하고, 비트마스크 j 로 표현된 도시들의 부분 집합을 방문한 최소 거리
3. 모든 도시 부분집합을 순회하며 dp 테이블을 채운다.